import collections


class Solution(object):
    def frogPosition(self, n, edges, t, target):
        d = collections.defaultdict(set)
        for u, v in edges:
            d[u].add(v)
            d[v].add(u)
        path = set()

        def dfs(i, p, k):
            path.add(i)
            if k == t:
                path.remove(i)
                if i == target:
                    return p
                else:
                    return 0
            t_count = 0
            next_path = set()
            for v in d[i]:
                if v not in path:
                    next_path.add(v)
                    t_count += 1
            if t_count == 0:
                path.remove(i)
                if i == target:
                    return p
                else:
                    return 0
            else:
                ans = 0
                for v in next_path:
                    ans += dfs(v, p / t_count, k + 1)
                path.remove(i)
                return ans

        return dfs(1, 1, 0)